package twentytwenty;

/**
 * @Author: Zahi
 * @Description:
 * @Date Created in 2020-12-08 10:32
 * @Modified By:
 */
public class CountPrimes_204 {
    public static void main(String [] args){
        int n = 10;
        System.out.println(countPrimes(n));
    }

    public static int countPrimes(int n){
        int count = 0;
        for (int i = 2; i < n; ++i) {
            count += isPrimes(i)? 1 : 0;
        }
        return count;
    }

    public static boolean isPrimes(int n){
        // 为了节约时间，降低时间复杂度 2*5和5*2没有差别
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0){
                return false;
            }
        }
        return true;
    }
}
